

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

template<class Containers>
void Print(const Containers& con)
{
    for (auto& c : con)
    {
        cout << c << " ";
    }
    cout << endl;
}

class Solution
{
    using Node = TreeNode;
public:
	void MyTest1()
	{
		int a = 23, b = 2, c = 5;
		a |= b;
		a ^= c;
		cout << a << endl;
		cout << (a | b ^ c) << endl;
	}

    bool CheckPermutation(string s1, string s2)
    {
        int sz1 = s1.size(), sz2 = s2.size();

        if (sz1 != sz2)
            return false;

        vector<int> cnt1(26);
        vector<int> cnt2(26);
        for (const auto& e : s1)
        {
            ++cnt1[e - 'a'];
        }
        for (const auto& e : s2)
        {
            ++cnt2[e - 'a'];
        }

        return cnt1 == cnt2;
    }

    bool searchMatrix1(vector<vector<int>>& matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();

        if (target > matrix[m - 1][n - 1] || target < matrix[0][0])
            return false;

        for (int row = 0, col = n - 1; row < m && col >= 0;)
        {
            if (matrix[row][col] > target)
                --col;
            else if (matrix[row][col] < target)
                ++row;
            else
                return true;
        }

        return false;
    }

    bool searchMatrix2(vector<vector<int>>& matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();

        if (target > matrix[m - 1][n - 1] || target < matrix[0][0])
            return false;

        for (int row = 0; row < m; ++row)
        {
            if (BFind(matrix[row], 0, n - 1, target))
                return true;
        }

        return false;
    }

    bool searchMatrix3(vector<vector<int>>& matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();

        if (target > matrix[m - 1][n - 1] || target < matrix[0][0])
            return false;

        for (int row = 0; row < m; ++row)
        {
            auto low = lower_bound(matrix[row].begin(), matrix[row].end(), target);
            if (low != matrix[row].end() && *low == target)
                return true;
        }

        return false;
    }

    Node* GetTree()
    {
        /*Node* node1 = new Node(1);
        Node* node2 = new Node(2);
        Node* node3 = new Node(3);
        Node* node4 = new Node(4);
        Node* node5 = new Node(5);
        Node* node8 = new Node(8);
        Node* node6 = new Node(6);
        Node* node7 = new Node(7);
        Node* node9 = new Node(9);

        node1->left = node2, node1->right = node3;
        node2->left = node4, node2->right = node5;
        node5->left = node6, node5->right = node7;
        node3->right = node8;
        node8->left = node9;*/

        Node* node1 = new Node(1);
        Node* node2 = new Node(2);
        Node* node3 = new Node(3);

        node1->right = node2;
        node2->left = node3;

        return node1;
    }

    vector<int> inorderTraversal(TreeNode* root)// err
    {
        if (nullptr == root)
            return {};

        vector<int> v;
        v.reserve(101);
        stack<Node*> t;

        t.push(root);
        while (!t.empty())
        {
            if (t.top()->left)
                t.push(t.top()->left);
            else
            {
                Node* top = t.top();
                v.push_back(top->val);
                t.pop();

                if (!t.empty())
                {
                    top = t.top();
                    v.push_back(top->val);
                    t.pop();
                }
                if (top->right)
                    t.push(top->right);
            }
        }

        return v;
    }

private:
    bool BFind(vector<int>& v, int lf, int rg, int tar)
    {
        while (lf <= rg)
        {
            int mid = lf + ((rg - lf) >> 1);

            if (v[mid] > tar)
                rg = mid - 1;
            else if (v[mid] < tar)
                rg = mid + 1;
            else
                return true;
        }

        return false;
    }
};

void Test1()
{
	Solution().MyTest1();
    Print(Solution().inorderTraversal(Solution().GetTree()));
}

bool isans(int i)
{
    if ((int)sqrt(i) != sqrt(i))
        return false;

    int n = i, cnt = 0;
    while (n)
    {
        n /= 10;
        ++cnt;
    }

    for (int j = 1; j < cnt; ++j)
    {
        int a = i / (int)pow(10, j);
        int b = i % (int)pow(10, j);
        int as = sqrt(a);
        int bs = sqrt(b);

        if (0 == as || 0 == bs)
            continue;
        if (a == as * as && b == bs * bs)
        {
            if (i == a * (int)pow(10, j) + b)
                return true;
        }
    }

    return false;
}

void Test2()
{
    int a = 169, b = 10000;
    //cin >> a >> b;

    for (int i = a; i <= b; ++i)
    {
        if (isans(i))
            cout << i << endl;
    }
}

int main()
{
	//Test1();
    Test2();

	return 0;
}